# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
class BinaryMatrix(object):
    def __init__(self, grid):
        self.grid = grid

    def get(self, row: int, col: int) -> int:
        return self.grid[row][col]

    def dimensions(self) -> list:
        return [len(self.grid), len(self.grid[0])]


class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        m, n = binaryMatrix.dimensions()
        left, right = 0, m
        while left < right:
            mid = (left + right) // 2
            find = False
            for i in range(m):
                if binaryMatrix.get(i, mid) == 1:
                    find = True
                    break

            if not find:
                left = mid + 1
            else:
                right = mid

        return left if left < n else -1


if __name__ == "__main__":
    print(Solution().leftMostColumnWithOne(BinaryMatrix([[0, 0], [1, 1]])))  # 0
    print(Solution().leftMostColumnWithOne(BinaryMatrix([[0, 0], [0, 1]])))  # 1
    print(Solution().leftMostColumnWithOne(BinaryMatrix([[0, 0], [0, 0]])))  # -1
    print(Solution().leftMostColumnWithOne(BinaryMatrix([[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1]])))  # 1
